package com.jump.datareciever.calculation;

import java.util.*;

/**
 * @author: chuanyi@88.com
 * @description:
 * @date: 2021/3/17 02:02
 */
public class TopK {
    public static void main(String[] args) {
        List<Double> xDataList = Arrays.asList(0.718039274, 0.83925283, 0.839923263, 0.568495214, 0.426614434, 0.630703211, 1.266213655, 1.658750534, 1.01800406, 0.602379262, 0.370852828, 0.085871212, 0.144984812, 0.245108813, -0.53142482, -0.026894402, 0.769273639, 0.936822414, 0.048063207, 0.783112884, 2.725355387, 1.924380064, 0.529025614, 0.38129282, 0.314214408, -0.672844827, -0.781054437, -0.10354241, 0.472978413, 0.024724003, 1.563195229, 2.418924809, 1.208558559, -0.475339234, -0.104079209, -0.626179278, -0.395304024, 0.208654419, 0.498303205, 0.011516803, 0.967681646, 1.906296134, 1.278785706, -0.281461626, -0.091869608, -0.338525623, -0.442970455, 0.013785601, 0.118999206, -0.203996807, 0.096844807, 1.725981712, 1.722413659, 0.614153683, -0.21233362, -0.220965624, -0.743726492, -0.387853622, 0.081664808, 0.333432823, -0.278351218, 0.871033669, 1.646315217, 1.111904025, 0.007634404, 0.126112819, -0.331856817, -0.757391214, -0.341639251, 0.32187441, 0.317864835, -0.0177192, 1.759316087, 1.708742499, 0.788364828, -0.087892003, -0.524622381, -0.677610457, -0.412520826, 0.084435202, 0.631850421, 0.213283211, 0.882220089, 2.548151255, 1.454089642, -0.087476, -0.071752012, -0.834500074, -0.531287968, 0.038776804, 0.510856032, 0.289184809, 0.369928032, 1.803411365, 1.873844981, 0.75936079, -0.049903203, -0.127310395, -0.63762641, -0.247418404, 0.068994403, 0.353423238, 0.080301598, 0.699802458, 1.960510492, 1.739195347, 0.181956813, -0.401191205, -0.678719282, -0.631729662, -0.023437602, 0.405744016, 0.610408068, -0.168705598, 1.208009005, 1.85973537, 1.33966887, -0.125576004, -0.309296042, -0.792717695, -0.557064056, -0.0163304, 0.48307842, 0.397629619, 0.169597596, 1.965740085, 1.936059475, 0.80803448, -0.467977613, -0.832596838, -0.728380859, -0.294862419, 0.250760823, 0.508190453, 0.017296005, 0.884904861, 2.009504795, 1.674521685, 0.52838403, -0.319869608, -0.705937684, -0.818493605, -0.183310419, 0.264981598, 0.417629629, 0.362039238, 1.69764185, 1.748847246, 1.02069211, -0.341448814, -0.215964809, -0.663504004, -0.550401628, 0.010224001, 0.471415222, 0.244406417, 0.517362416, 1.958839297, 2.077603102, 0.98512733, -0.229223207, -0.539948881, -0.791828036, -0.356965631, 0.107434407, 0.568632066, 0.151170418, 1.149556041, 1.973161697, 1.875293612, 0.411173612, -0.769737661, -0.563939214, -0.581400871, -0.0441048, 0.414188802, 0.587621629, 0.188812807, 1.995827317, 2.803677559, 1.031119347, -0.704517603, -1.240901709, -0.856816053, -0.007656801, 0.483952016, 0.999926448, 0.469130427, 1.678512096, 2.399036169, 1.117676973, -0.555761635, -0.72870481, -0.985044837, -0.013655202, 0.54583919, 0.95692724, 0.451014429, 1.944939256, 2.601472855, 0.759017646, -0.374433637, -0.520168066, -0.812393665, 0.058116004, 0.496733636, 0.753826439, 0.484355211, 1.790950418, 2.41536665, 1.083783269, -0.328000009, -0.497060806, -0.745610476, -0.303748786, 0.172428817, 0.605178416, 0.381826431, 1.079100132, 2.34514904, 1.72540009, 0.507939219, -0.32720241, -0.701054454, -0.597175181, -0.028552802, 0.544848025, 0.602827251, 0.688450456, 2.190378428, 2.115830421, 0.485159278, -0.585416853, -0.497499257, -0.719840884, -0.028994404, 0.542398393, 0.82960403, 0.313816816, 1.362312078, 2.278267145, 1.29543364, 0.048298407, -0.0430976, -0.528959215, -0.562957585, -0.086770408, 0.437302411, 0.47139284, 0.644784033, 2.395255566, 2.234251261, 0.989680052, -0.290214419, -0.79160881, -0.514284015, -0.18620801, 0.30619204, 0.802719295, 0.471834391, 0.392695248, 1.975944877, 2.378362656, 1.127554536, -0.113452002, -0.652168036, -0.816047251, -0.326970428, 0.260641605, 0.833273649, 0.501270413, 0.634896815, 2.307372808, 2.157927275, 0.853578389, -0.342220813, -0.2859568, -0.850944817, -0.272308022, 0.352749616, 0.726611257, 0.428708017, 1.148536086, 2.493025064, 1.876049757, 0.739249647, -0.0011024, -1.11058557, -1.114032865, 0.119784005, 0.635608852, 0.983370483, 0.366137624, 1.60440886, 2.33393383, 0.953447998, 0.0816456, -0.321972817, -0.555948794, -0.65073204, -0.0154376, 0.404187232, 0.634500027, 0.52457118, 2.098391294, 1.935722589, 0.802477658, -0.419320017, -0.557276845, -0.775828123, -0.369524837, 0.262093604, 0.583964825, 0.020759204, 0.055948805, 1.846416831, 1.88595295, 0.836476028, -0.369439214, -0.361731261, -0.804606438, -0.480514437, 0.089331202, 0.409861654, 0.219088003, 0.048292007, 1.259322405, 2.343487263, 1.369317651, 0.059313606, -0.746284008, -0.610827267, -0.538290441, -0.050881606, 0.344079196, 0.667729676, 0.285521626, 0.068606406, 1.898731351, 2.498346567, 1.618969679, -0.0199176, -0.478064805, -0.935036838, -0.68183285, 0.0128928, 0.509959996, 0.612063289, 0.168600008, 1.660869718, 1.76472652, 1.406883955, 0.112082399, -0.521528065, -0.224848017, -0.674954414, -0.278862417, 0.148432016, 0.503523231, 0.163745612, 0.387135208, 2.486591339, 2.208465576, 1.267665744, -0.241677612, -0.383272022, -1.492793798, -0.539170444, 0.450859219, 0.881489694, 0.488282442, 0.113912024, 2.715026379, 2.408904076, 0.909019291, -0.559650481, -0.522941589, -0.776492059, -0.49740085, -0.005334399, 0.554735243, 0.652736843, -0.229935214, 1.551528931, 2.652001858, 2.116592884, 0.610817611, -0.505639195, -0.766484022, -0.88304323, -0.234087199, 0.378633618, 0.827932835, 0.714725673, -0.131561607, -0.253328025, 0.362188816, 0.870153666, 0.672920883, 0.96225208, 0.667259276, 0.677607298, 0.363516808, 0.144425601, 0.087768003, 0.061213601, 0.124206401, 0.314191997, 0.458957613, 0.473064005, 0.489623219, 0.285737634, 0.538401663, 0.357292801, 0.369963199, 0.373966455, 0.232641608, 0.162316009, 0.131208807, 0.110322401, 0.078764014, 0.278757602, 0.176644817);
        List<Integer> yDataList = Arrays.asList(-48, 380, 1152, 1984, 2268, 2476, 2160, 1452, 484, 948, 1464, 2048, 1160, 448, 124, 448, 884, 1164, 1460, 1256, 1588, 2388, 1704, 1516, -84, -420, 124, 520, 1320, 1608, 1724, 2572, 1844, 1536, -124, -304, 68, 468, 1144, 1860, 1704, 2008, 2052, 1460, 244, -260, -68, 272, 896, 1376, 1588, 1832, 2580, 1824, 1308, -96, -228, 36, 432, 1052, 1944, 2088, 1812, 1924, 1484, 528, -480, -160, 232, 764, 1200, 1712, 2252, 2464, 1684, 1004, 52, -184, 76, 96, 644, 1344, 2084, 2600, 2252, 1464, -32, -404, 84, 248, 700, 1588, 1668, 1908, 2336, 1780, 1016, 148, -72, 236, 292, 748, 1604, 1612, 2192, 2364, 1672, 236, -216, -88, 328, 352, 828, 1928, 2048, 2460, 1648, 1124, 168, -200, 252, 320, 648, 1356, 1716, 2456, 2584, 1764, 816, 60, -36, 136, 236, 604, 1572, 1776, 2716, 2672, 1680, 512, -248, -16, 232, 584, 1368, 1968, 2196, 2556, 1884, 1348, -24, -116, 256, 284, 588, 1276, 1640, 2568, 2736, 1728, 1000, 240, 48, 124, 132, 392, 1552, 2044, 3104, 2700, 1444, 648, -116, 132, 68, 104, 544, 1504, 3240, 2888, 1720, 576, -76, 20, 232, 280, 848, 1604, 2324, 2452, 1820, 848, 76, 28, 52, 64, 808, 1724, 2408, 2696, 1684, 728, 80, -4, 104, 172, 684, 1924, 2556, 2752, 1544, 804, -52, -176, 196, 344, 624, 1472, 1768, 2568, 2280, 1500, 508, 36, 136, -196, 124, 1368, 1800, 2844, 2400, 1628, 764, 236, 8, -32, 88, 936, 1792, 2248, 2532, 1988, 1176, 372, -276, 140, 12, 204, 1160, 1876, 3116, 2716, 1824, 852, 184, -28, 52, 44, 376, 1148, 1876, 2600, 2784, 1848, 776, 320, -176, 80, 96, 628, 1544, 1776, 2348, 2352, 1684, 992, 60, 216, 276, 336, 632, 1280, 2144, 2008, 2256, 1584, 416, -4, 396, 380, 292, 1208, 1796, 2144, 2056, 1688, 984, 380, -108, 372, 284, 560, 1288, 2036, 2696, 2296, 1596, 748, -92, 12, 256, 400, 604, 1496, 1792, 2252, 2356, 1520, 1176, 136, -188, 152, 180, 460, 1468, 1996, 2484, 2420, 1984, 1172, 496, 116, 88, 84, 244, 260, 1144, 1768, 2224, 2960, 2320, 1412, 376, -300, 268, 248, 484, 1108, 2220, 2380, 2004, 2044, 1244, 816, 124, 188, 236, 212, 540, 1348, 1752, 2116, 2544, 1804, 1596, 200, -96, 272, 104, 200, 1200, 2172, 2720, 2548, 1576, 972, 252, -68, 160, 72, 324, 528, 1812, 2388, 2932, 2236, 1304, 1076, 152, -40, 156, 292, 488, 896, 1260, 1160, 1400, 1212, 1516, 1408, 916, 1616, 1172, 1040, 988, 680, 664, 960, 772, 756, 712, 800, 916, 1168, 1088, 1264, 1240, 1088, 1204, 1008, 952, 1052, 1120);
        List<Integer> zDataList = Arrays.asList(480, -124, -176, -380, -344, 136, -376, -40, 172, 0, 664, 1184, 1372, 1904, 1484, 812, 560, 100, -172, -388, -52, 72, 1252, 2128, 1736, 1356, 1104, 660, 572, 304, 436, 4, 472, 1656, 1952, 1568, 896, 656, 304, 164, 192, -100, 40, 1456, 2124, 1428, 920, 732, 424, 136, 204, 284, 184, 1040, 1532, 1676, 1444, 1008, 364, 212, 336, 256, 208, 428, 1192, 1800, 1500, 1224, 540, 220, 92, 184, 152, 916, 1064, 1496, 1340, 1352, 1200, 652, 100, 472, 416, 792, 832, 1532, 1772, 1240, 988, 780, 384, 192, 320, 424, 552, 1132, 1480, 1448, 1292, 956, 676, 140, 144, 412, 440, 756, 1648, 1700, 1380, 1060, 640, 356, 4, -20, 644, 768, 884, 1128, 1728, 1436, 1120, 716, 444, -16, 340, 580, 808, 1176, 1392, 1576, 1236, 1160, 568, 192, 220, 432, 264, 668, 1108, 1488, 1664, 1392, 1076, 508, 140, 380, 396, 520, 840, 1036, 1420, 1504, 1228, 892, 448, -36, 168, 456, 632, 1064, 1148, 1476, 1340, 1216, 916, 272, 76, 300, 888, 772, 1080, 1280, 1428, 1200, 904, 764, 284, 476, 920, 948, 1368, 1632, 1632, 1368, 996, 364, -140, -16, 720, 760, 944, 1728, 1928, 992, 1164, 816, -492, 256, 564, 776, 1368, 1668, 1648, 1156, 1152, 592, -68, 8, 280, 640, 1092, 1360, 1484, 1348, 988, 648, 184, -244, 304, 244, 928, 1064, 1496, 1508, 1368, 988, 432, -360, 524, 172, 912, 1004, 1316, 1452, 1208, 952, 568, -96, 28, 128, 132, 916, 960, 1536, 1404, 1036, 844, 604, -108, 216, 200, 1076, 992, 1236, 1168, 1552, 1232, 668, 164, -384, 136, 408, 992, 956, 1420, 1644, 1260, 1068, 636, -136, -72, -72, 524, 300, 1112, 1300, 1244, 1404, 972, 572, 264, -20, 68, 224, 536, 836, 1584, 1816, 1012, 976, 468, -592, 148, 248, 468, 740, 1076, 1300, 1368, 1428, 844, 652, 12, 412, 160, 860, 776, 908, 1176, 1460, 1020, 668, 76, -112, 252, 820, 484, 964, 1164, 1088, 856, 980, 808, 460, -324, 424, 540, 744, 688, 1060, 1360, 1276, 1080, 888, 652, 128, -68, 164, 984, 724, 1080, 1092, 1356, 1124, 1096, 768, 472, 240, 124, -124, 568, 308, 1100, 1236, 1220, 1040, 856, 548, 208, 212, 400, 840, 564, 1012, 1232, 1256, 1240, 1176, 800, 528, -320, 432, 1284, 596, 1240, 1288, 1516, 1088, 984, 628, 592, 440, 104, 824, 488, 1000, 1164, 1508, 1360, 1112, 960, 532, 260, -196, -312, 340, -132, 600, 232, 704, 824, 840, 1164, 952, 560, 472, 364, 444, 360, 424, 368, 4, 268, 60, 180, 136, -40, 0, -28, -128, -404, -252, -476);
        System.out.println("x top k:" + solutionByHeap0(xDataList, 40));
        System.out.println("y top k:" + solutionByHeap1(yDataList, 40));
        System.out.println("z top k:" + solutionByHeap1(zDataList, 40));
        System.out.println("x top k:" + solutionByHeap0(xDataList, 40).stream().min((x, y) -> (int) (x - y)));
        System.out.println("y top k:" + solutionByHeap1(yDataList, 40).stream().min(Comparator.comparingInt(x -> x)));
        System.out.println("z top k:" + solutionByHeap1(zDataList, 40).stream().min(Comparator.comparingInt(x -> x)));
    }

    public static List<Double> solutionByHeap0(List<Double> input, int k) {
        List<Double> list = new ArrayList<>();
        if (k > input.size() || k == 0) {
            return list;
        }
        Queue<Double> queue = new PriorityQueue<>();
        for (Double num : input) {
            if (queue.size() < k) {
                queue.add(num);
            } else if (queue.peek() < num) {
                queue.poll();
                queue.add(num);
            }
        }
        while (k-- > 0) {
            list.add(queue.poll());
        }
        return list;
    }

    public static List<Integer> solutionByHeap1(List<Integer> input, int k) {
        List<Integer> list = new ArrayList<>();
        if (k > input.size() || k == 0) {
            return list;
        }
        Queue<Integer> queue = new PriorityQueue<>();
        for (Integer num : input) {
            if (queue.size() < k) {
                queue.add(num);
            } else if (queue.peek() < num) {
                queue.poll();
                queue.add(num);
            }
        }
        while (k-- > 0) {
            list.add(queue.poll());
        }
        return list;
    }
}
